package stack;

import java.util.ArrayList;
import java.util.Stack;

public class p234 {
    public static void main(String[] args) {

    }
}


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class test02 {

//    /**
//     * 题目：回文链表
//     * 解法：转置+快慢指针（找到中间值）+循环遍历
//     *重点就是快慢指针找中间点
//     * */
//    public boolean isPalindrome(ListNode head){
//        //设置快慢指针
//        ListNode fast=head;
//        ListNode slow=head;
//
//        //找到中间节点
//        while(fast!=null&&fast.next!=null){
//            slow=slow.next;
//            fast=fast.next.next;
//        }
//
//        //如果是奇数，那么就在进下一位
//        if(fast!=null){
//            slow=slow.next;
//        }
//
//        //反转中间点
//        slow=reversal(slow);
//        fast=head;
//        while(fast!=null){
//            if(fast.val!=slow.val){
//                return false;
//            }
//            fast=fast.next;
//            slow=slow.next;
//        }
//        return true;
//
//    }
//
//    public ListNode reversal(ListNode head){
//        ListNode cur=null;
//
//        while (head!=null){
//            ListNode node=head.next;
//            head.next=cur;
//            cur=head;
//            head=node;
//        }
//        return cur;
//    }

    /**
     * 解法2：栈
     * */
//    public boolean isPalindrome(ListNode head){
//        //建立栈，用栈来存储，再弹栈，相当于转置
//        Stack<Integer> stack=new Stack<>();
//
//        ListNode temp=head;
//        //压栈
//        while (temp!=null){
//            stack.push(temp.val);
//            temp=temp.next;
//        }
//
//        //出栈比较
//        while(head!=null){
//            if(head.val!=stack.pop()) {
//                return false;
//            }
//            head=head.next;
//        }
//        return true;
//
//    }

    /**
     * 解法3：递归
     *
     * */
//    ListNode temp;
//    public boolean isPalindrome(ListNode head){
//        temp=head;
//        return check(head);
//    }
//
//    private boolean check(ListNode head){
//        if(head==null){
//            return true;
//        }
//        boolean res=check(head.next)&&(head.val== temp.val);
//        temp=temp.next;
//        return res;
//    }

    /**
     * 解法4：数组存储，然后遍历
     * */

    public boolean isPalindrome(ListNode head){
        ArrayList<Integer> arrayList=new ArrayList<>();
        while(head!=null){
            arrayList.add(head.val);
            head=head.next;
        }
        int length=arrayList.size();
        for(int i=0,j=length;i<length&&j>=0;j--,i++){
            if(arrayList.get(i)!=arrayList.get(j)){
                return false;
            }
        }
        return true;
    }





}